package com.sicheng.algorithm.dynamic;

/**
 * @author zsc
 * @version 1.0
 * @date 2021/10/30 15:56
 */
public class 样本收集问题 {
    /**

     * 题目描述：机器人R在一个有n×n个方格区域F中收集样本。（i,j）方格中样本的
     *
     * 价值为v(i,j)，如图所示，R从方形区域F的左上角A点出发，向下或向右行走，直到右
     *
     * 下角的B点，在走过的路上，收集方格中的样本。R从A点到B点共走2次，试找出R的
     *
     * 2条行走路径，使其取得的样本总价值最大。
     *
     * 分析：
     * 性质1：机器人R从A点走到B点的一条路径的方格数为2*n-1
     *
     * 性质2：记机器人R的当前坐标是N（X,Y），从起点A到当前点N的路径方格数是steps，
     * 则有steps = x+y—1
     *
     * 原文链接：https://blog.csdn.net/weixin_43958091/article/details/102332184
     *
     */
    public static void main(String[] args) {

    }

    /**
     *
     * 此题可用动态规划解答，机器人走的步数将问题划分为  2 * n-1个状态.
     *
     * 题目要求R从A到B共走两次，如果分两次来走的话，
     * 一个就是效率低下问题，
     * 另一个就是难以标记那些点是
     * 在第一次已经走过，对重复走两次的点所造成的误差难以消除。
     * 有个办法就是同时走两条路径，当两条路径走到相同一点时，只对相同点取值一次。
     *
     * 由性质2我们知道，在一定的Steps的情况下，
     * 如果知道当前点的X轴坐标，
     * 就可以知道Y轴坐标Y=Steps—X+1，
     * 所以可以记dp[Steps][x1][x2]为两条路径同时走Steps步的情况下，
     * 到达（x1，y1）(x2,y2)所取的当前最大值。
     * 由于机器人只能向下和向左走，那么在（x1，y1）(x2,y2)的
     * 前一个状态就是一下四种之一：
     *
     * （x1，y1-1）(x2,y2-1)；
     *
     * （x1，y1-1）(x2-1,y2)；
     *
     * （x1-1，y1）(x2-1,y2)
     *
     * （x1-1，y1）(x2,y2-1)
     *
     * 当（x1，y1）(x2,y2)是不同点的情况下，状态转移方程如下：
     *
     *        dp[Steps][x1][x2]=max{
     *
     * 			   dp[steps-1][x1][x2]+mp[x1][y1]+mp[x2][y2],
     *
     *             dp[steps-1][x1][x2-1]+mp[x1][y1]+mp[x2][y2],
     *
     *             dp[steps-1][x1-1][x2]+mp[x1][y1]+mp[x2][y2],
     *
     *             dp[steps-1][x1-1][x2-1]+mp[x1][y1]+mp[x2][y2]
     *         }
     *
     * 当（x1，y1）(x2,y2)是相同点的情况下，状态转移方程如下：
     *
     *        dp[steps][x1][x2] = max{
     *
     * 		       dp[steps-1][x1][x2]+mp[x1][y1]，
     *
     * 		       dp[steps-1][x1][x2-1]+mp[x1][y1]，
     *
     * 		       dp[steps-1][x1-1][x2]+mp[x1][y1]，
     *
     * 		       dp[steps-1][x1-1][x2-1]+mp[x1][y1]
     *         }
     * 原文链接：https://blog.csdn.net/weixin_43958091/article/details/102332184
     */
    public static int robot(int[][] mp){


        return -1;
    }
}
